package com.brett.frame.learn.sort.choose;

import com.brett.frame.learn.sort.base.Sort;
import com.brett.frame.learn.util.DataBuilder;

/**
 * 树选择排序
 * @author lenovo
 *是一种按照锦标赛的思想进行选择排序的方法，即所有记录采取两两分组，筛选出较小（较大）的值；然后从筛选出的较小（较大）值中再两两分组选出更小（更大）值，依次类推，直到最后选出一个最小（最大）值。同样可以采用此方式筛选出次小（次大）值等。
 *时间复杂度为O(nlogn)
 */
public class TreeChooseSort implements Sort {

	DataBuilder builder = new DataBuilder();

	@Override
	public int[] sort(int[] arr) {
		int len = arr.length;
		int treeNodeSize = 2 * len - 1;
		int[] tree = new int[treeNodeSize+1];

		for (int i = len - 1, j = 0; i >= 0; j++, i--) {
			tree[treeNodeSize - j] = arr[i];
		}
		builder.printArr("放在tree最后：", tree);
		
		for(int i=treeNodeSize-len;i>=0;i--) {
			tree[i]=tree[2*i]>tree[2*i+1]?tree[2*i]:tree[2*i+1];
		}
		builder.printArr("tree求和后：", tree);
		builder.printHeapArr(tree);
		return arr;
	}

}
